{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_dict = {-1:np.array([[1,7],\n",
    "                          [2,8],\n",
    "                          [3,8],]),\n",
    "             \n",
    "             1:np.array([[5,1],\n",
    "                         [6,-1],\n",
    "                         [7,3],])}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{-1: array([[1, 7],\n",
       "        [2, 8],\n",
       "        [3, 8]]), 1: array([[ 5,  1],\n",
       "        [ 6, -1],\n",
       "        [ 7,  3]])}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAADrBJREFUeJzt3WFoJPd9xvHn0WmdRqcIN5wors9UiTAuwYjYWdy4B6bYaYka4/SFDA5IUEPZBiWpfT0ITt+EvMqbXi59URKOdUJ6cmPqtQMlsdIEEtMGGrersyvXPgdHrhNf7PQUTGspor2N79cXuy53Ouk0u9rZ2f/c9wPHSqM/q99g/L3RaObGESEAQDpGih4AANAdwg0AiSHcAJAYwg0AiSHcAJAYwg0AiSHcAJAYwg0AiSHcAJCY0Tze9NChQzE1NZXHWwNAKa2srPwiIiazrM0l3FNTU2o2m3m8NQCUku2fZF3LqRIASAzhBoDEEG4ASAzhBoDEEO4+WntjTYvfWtTE5yc08rkRTXx+QovfWtTaG2tFj9aVsuwHUFbO8iAF20cl/YmkkPScpPsj4n92W1+tVuNqu6pk+aVlzT02p9ZbLbUutP5/e2WkosqBihr3NjR742yBE2ZTlv0AUmN7JSKqWdbuecRt+3pJfyapGhE3Szog6b79jVgua2+sae6xOW21ti6JnSS1LrS01drS3GNzQ3/EWpb9AMou66mSUUnvtD0qaUzSa/mNlJ7j/3xcrbdaV1zTequlEz88MaCJelOW/QDKbs9wR8TPJP2lpJ9Kel3Sf0fEd/IeLCVLq0uXHaFu17rQ0qnVUwOaqDdl2Q+g7LKcKvl1SR+V9B5JvynpoO35HdbVbDdtN9fX1/s/6RDbPL/Z13VFKct+AGWX5VTJhyT9R0SsR0RL0hOSfnf7oog4GRHViKhOTma63b40xq8Z7+u6opRlP4CyyxLun0r6oO0x25Z0l6Qz+Y6VlvmZeVVGKldcUxmpaGFmYUAT9aYs+wGUXZZz3E9Lakg6rfalgCOSTuY8V1KO3X5MlQN7BO9ARUc/eHRAE/WmLPsBlF2mq0oi4rMR8dsRcXNELETE/+Y9WEqm3z2txr0NjVXGLjtirYxUNFYZU+PehqbfPV3QhNmUZT+AsuPOyT6ZvXFWqx9fVe0DNU28Y0IjHtHEOyZU+0BNqx9fTeamlbLsB1Bmme6c7NbVeOckAOxHX++cBAAMF8INAIkh3ACQGMINAIkh3ACQGMINAIkh3ACQGMINAIkh3ACQmKEJNw+oBYBshiLcyy8ta+bLM6qfrmvj/IZCoY3zG6qfrmvmyzNafmm56BEBYGgUHm4eUAsA3Sk83DygFgC6U3i4eUAtAHSn8HDzgFoA6E7h4eYBtQDQncLDzQNqAaA7hYebB9QCQHcKDzcPqAWA7hQebokH1AJAN3hYMAAMAR4WDAAlRrgBIDGEGwASQ7gBIDGEGwASQ7gBIDGEGwASQ7gBIDGEGwASQ7gBIDGEGwASkynctq+13bD9ou0ztm/PezAAwM5GM677K0nfjog529dIGstxJgDAFewZbtsTku6Q9MeSFBHnJZ3PdywAwG6ynCp5r6R1SV+1/Yztuu2DOc8FANhFlnCPSrpV0pci4hZJv5T00PZFtmu2m7ab6+vrfR4TAPC2LOE+K+lsRDzd+byhdsgvEREnI6IaEdXJycl+zggAuMie4Y6In0t61fZNnU13SXoh16kAALvKelXJpyQ90rmi5GVJ9+c3EgDgSjKFOyKelZTpWWgAgHxx5yQAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiCDcAJIZwA0BiMofb9gHbz9j+Zp4DAQCurJsj7gcknclrEABANpnCbfuwpI9Iquc7DgBgL1mPuL8o6dOSLuQ4CwAggz3DbftuSeciYmWPdTXbTdvN9fX1vg0IALhUliPuI5Lusf2KpEcl3Wl7afuiiDgZEdWIqE5OTvZ5TADA2/YMd0R8JiIOR8SUpPskfS8i5nOfDACwI67jBoDEjHazOCKekvRULpMAADLhiBsAEkO4ASAxhBsAEkO4ASAxhBsAEkO4ASAxhBsAEkO4ASAxhBsAEkO4ASAxhBsAEkO4AaAba2vS4qI0MSGNjLRfFxfb2weEcANAVsvL0syMVK9LGxtSRPu1Xm9vX14eyBiEGwCyWFuT5uakrS2p1br0a61We/vc3ECOvAk3AGRx/Pjlwd6u1ZJOnMh9FMINAFksLWUL96lTuY9CuAEgi83N/q7bB8INAFmMj/d33T4QbgDIYn5eqlSuvKZSkRYWch+FcANAFseOZQv30aO5j0K4ASCL6Wmp0ZDGxi4PeKXS3t5otNfljHADQFazs9LqqlSrXXrnZK3W3j47O5AxHBF9f9NqtRrNZrPv7wsAZWV7JSKqWdZyxA0AiSHcAJAYwg0AiSHcAJAYwg0AiSHcAJAYwg0AiSHcAJAYwg0AiSHcAJAYwg0Aidkz3LZvsP1922dsP2/7gUEMBgDY2WiGNb+SdCwiTtt+l6QV29+NiBdyng0AsIM9j7gj4vWION35eEPSGUnX5z0YAGBnXZ3jtj0l6RZJT+cxDABgb5nDbXtc0uOSHoyIN3f4es1203ZzfX29nzMCAC6SKdy2K2pH+5GIeGKnNRFxMiKqEVGdnJzs54wAgItkuarEkh6WdCYivpD/SACAK8lyxH1E0oKkO20/2/nzhznPBQDYxZ6XA0bEDyR5ALMAADLgzkkASAzhBoDEEG4ASAzhBoDEEG4ASAzhBoDEEG4ASAzhBoDEEG4ASAzhBoDEEG4ASAzhBobd2pq0uChNTEgjI+3XxcX2dlyVCDcwzJaXpZkZqV6XNjakiPZrvd7evrxc9IQoAOEGhtXamjQ3J21tSa3WpV9rtdrb5+Y48r4KEW5gWB0/fnmwt2u1pBMnBjMPhgbhBobV0lK2cJ86NZh5MDQINzCsNjf7uw6lQbiBYTU+3t91KA3CDQyr+XmpUrnymkpFWlgYzDwYGoQbGFbHjmUL99Gjg5kHQ4NwA8NqelpqNKSxscsDXqm0tzca7XW4qhBuYJjNzkqrq1Ktdumdk7Vae/vsbNETogCOiL6/abVajWaz2ff3BYCysr0SEdUsazniBoDEEG4ASAzhBoDEEG4ASAzhBoDEEG4ASAzhBoDEEG4ASAzhBoDEEG4ASAzhBoDEZAq37Q/b/pHtH9t+KO+hAAC72zPctg9I+mtJs5LeJ+ljtt+X92AAgJ1lOeK+TdKPI+LliDgv6VFJH813LADAbrKE+3pJr170+dnONgBAAbKE2ztsu+wf8bZds9203VxfX9//ZACAHWUJ91lJN1z0+WFJr21fFBEnI6IaEdXJycl+zQcA2CZLuP9V0o2232P7Gkn3Sfr7fMcCAOxmdK8FEfEr25+U9A+SDkj6SkQ8n/tkAIAd7RluSYqIJyU9mfMsAIAMuHMSABJDuAEgMYQbABJDuAEgMYQbABJDuAEgMYQbABJDuAEgMYQbABJDuAEgMYQbABJDuAEMxtqatLgoTUxIIyPt18XF9nZ0hXADyN/ysjQzI9Xr0saGFNF+rdfb25eXi54wKYQbQL7W1qS5OWlrS2q1Lv1aq9XePjfHkXcXCDeAfB0/fnmwt2u1pBMnBjNPCRBuAPlaWsoW7lOnBjNPCRBuAPna3OzvOhBuADkbH+/vOhBuADmbn5cqlSuvqVSkhYXBzFMChBtAvo4dyxbuo0cHM08JEG4A+ZqelhoNaWzs8oBXKu3tjUZ7HTIh3ADyNzsrra5Ktdqld07Wau3ts7NFT5gUR0Tf37RarUaz2ez7+wJAWdleiYhqlrUccQNAYgg3ACSGcANAYgg3ACSGcANAYgg3ACSGcANAYnK5jtv2uqSf7OMtDkn6RZ/GKUoZ9kFiP4YN+zFc+rkfvxURk1kW5hLu/bLdzHoh+rAqwz5I7MewYT+GS1H7wakSAEgM4QaAxAxruE8WPUAflGEfJPZj2LAfw6WQ/RjKc9wAgN0N6xE3AGAXQxNu21+xfc72vxc9y37YvsH2922fsf287QeKnqkXtn/N9r/Y/rfOfnyu6Jn2w/YB28/Y/mbRs/TK9iu2n7P9rO1k/91k29fabth+sfP/ye1Fz9Qt2zd1/ju8/edN2w8O7PsPy6kS23dI2pT0NxFxc9Hz9Mr2dZKui4jTtt8laUXSH0XECwWP1hXblnQwIjZtVyT9QNIDEfHDgkfrie0/l1SVNBERdxc9Ty9svyKpGhFJX/9s+2uS/iki6ravkTQWEf9V9Fy9sn1A0s8k/U5E7Of+lcyG5og7Iv5R0htFz7FfEfF6RJzufLwh6Yyk64udqnvRttn5tNL5Mxx/y3fJ9mFJH5FUL3qWq53tCUl3SHpYkiLifMrR7rhL0tqgoi0NUbjLyPaUpFskPV3sJL3pnF54VtI5Sd+NiCT3Q9IXJX1a0oWiB9mnkPQd2yu2a0UP06P3SlqX9NXOqau67YNFD7VP90n6+iC/IeHOie1xSY9LejAi3ix6nl5ExFsR8X5JhyXdZju5U1i275Z0LiJWip6lD45ExK2SZiV9onN6MTWjkm6V9KWIuEXSLyU9VOxIveuc6rlH0mOD/L6EOwedc8KPS3okIp4oep796vwo+5SkDxc8Si+OSLqnc374UUl32l4qdqTeRMRrnddzkr4h6bZiJ+rJWUlnL/rpraF2yFM1K+l0RPznIL8p4e6zzi/1HpZ0JiK+UPQ8vbI9afvazsfvlPQhSS8WO1X3IuIzEXE4IqbU/pH2exExX/BYXbN9sPPLbnVOLfyBpOSuwIqIn0t61fZNnU13SUrqF/fbfEwDPk0itX9sGQq2vy7p9yQdsn1W0mcj4uFip+rJEUkLkp7rnB+WpL+IiCcLnKkX10n6Wuc35iOS/i4ikr2UrgR+Q9I32scFGpX0txHx7WJH6tmnJD3SOc3wsqT7C56nJ7bHJP2+pD8d+PcelssBAQDZcKoEABJDuAEgMYQbABJDuAEgMYQbABJDuAEgMYQbABJDuAEgMf8H7dZWUEqrcZIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "colors = {1:'r',-1:'g'}\n",
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(1,1,1)\n",
    "[[ax.scatter(x[0],x[1],s=100,color=colors[i]) for x in data_dict[i]] for i in data_dict]\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yi: -1\n",
      "featureset: [1 7]\n",
      "feature: 1\n",
      "feature: 7\n",
      "featureset: [2 8]\n",
      "feature: 2\n",
      "feature: 8\n",
      "featureset: [3 8]\n",
      "feature: 3\n",
      "feature: 8\n",
      "yi: 1\n",
      "featureset: [5 1]\n",
      "feature: 5\n",
      "feature: 1\n",
      "featureset: [ 6 -1]\n",
      "feature: 6\n",
      "feature: -1\n",
      "featureset: [7 3]\n",
      "feature: 7\n",
      "feature: 3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 7, 2, 8, 3, 8, 5, 1, 6, -1, 7, 3]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_data = []\n",
    "for yi in data_dict:\n",
    "    print('yi:', yi)\n",
    "    for featureset in data_dict[yi]:\n",
    "        print('featureset:', featureset)\n",
    "        for feature in featureset:\n",
    "            print('feature:', feature)\n",
    "            all_data.append(feature)         \n",
    "all_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8 -1\n"
     ]
    }
   ],
   "source": [
    "max_feature_value = max(all_data)\n",
    "min_feature_value = min(all_data)\n",
    "print(max_feature_value, min_feature_value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimized a step!\n",
      "Optimized a step!\n",
      "Optimized a step!\n",
      "[1 7] : 1.271999999999435\n",
      "[2 8] : 1.271999999999435\n",
      "[3 8] : 1.0399999999995864\n",
      "[5 1] : 1.0479999999990506\n",
      "[ 6 -1] : 1.7439999999985962\n",
      "[7 3] : 1.0479999999990506\n"
     ]
    }
   ],
   "source": [
    "def train(data):\n",
    "    # 参数字典 { ||w||: [w,b] }\n",
    "    opt_dict = {}\n",
    "\n",
    "    # 数据转换列表\n",
    "    transforms = [[1,1],\n",
    "                  [-1,1],\n",
    "                  [-1,-1],\n",
    "                  [1,-1]]\n",
    "\n",
    "    # 从字典中获取所有数据\n",
    "    all_data = []\n",
    "    for yi in data:\n",
    "        for featureset in data[yi]:\n",
    "            for feature in featureset:\n",
    "                all_data.append(feature)\n",
    "\n",
    "    # 获取数据最大最小值\n",
    "    max_feature_value = max(all_data)\n",
    "    min_feature_value = min(all_data)\n",
    "    all_data = None\n",
    "\n",
    "    # 定义一个长列表\n",
    "    step_sizes = [max_feature_value * 0.1,\n",
    "                  max_feature_value * 0.01,\n",
    "                  max_feature_value * 0.001\n",
    "                  ]\n",
    "\n",
    "\n",
    "    # 参数b的范围设置\n",
    "    b_range_multiple = 2\n",
    "    b_multiple = 5\n",
    "    latest_optimum = max_feature_value*10\n",
    "\n",
    "    # 基于不同步长训练优化\n",
    "    for step in step_sizes:\n",
    "        w = np.array([latest_optimum,latest_optimum])\n",
    "        # 凸优化\n",
    "        optimized = False\n",
    "        while not optimized:\n",
    "            for b in np.arange(-1*(max_feature_value*b_range_multiple),\n",
    "                               max_feature_value*b_range_multiple,\n",
    "                               step*b_multiple):\n",
    "                for transformation in transforms:\n",
    "                    w_t = w*transformation\n",
    "                    found_option = True\n",
    "\n",
    "                    for i in data:\n",
    "                        for xi in data[i]:\n",
    "                            yi=i\n",
    "                            if not yi*(np.dot(w_t,xi)+b) >= 1:\n",
    "                                found_option = False\n",
    "                                # print(xi,':',yi*(np.dot(w_t,xi)+b))\n",
    "\n",
    "                    if found_option:\n",
    "                        opt_dict[np.linalg.norm(w_t)] = [w_t,b]\n",
    "\n",
    "            if w[0] < 0:\n",
    "                optimized = True\n",
    "                print('Optimized a step!')\n",
    "            else:\n",
    "                w = w - step\n",
    "\n",
    "        norms = sorted([n for n in opt_dict])\n",
    "        #||w|| : [w,b]\n",
    "        opt_choice = opt_dict[norms[0]]\n",
    "        w = opt_choice[0]\n",
    "        b = opt_choice[1]\n",
    "        latest_optimum = opt_choice[0][0]+step*2\n",
    "\n",
    "    for i in data:\n",
    "        for xi in data[i]:\n",
    "            yi=i\n",
    "            print(xi,':',yi*(np.dot(w,xi)+b)) \n",
    "    return w, b\n",
    "            \n",
    "    \n",
    "w, b = train(data_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 定义预测函数\n",
    "def predict(features):\n",
    "    # sign( x.w+b )\n",
    "    classification = np.sign(np.dot(np.array(features),w)+b)\n",
    "    if classification !=0:\n",
    "        ax.scatter(features[0], features[1], s=200, marker='^', c=colors[classification])\n",
    "        print(classification)\n",
    "    return classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1.0\n",
      "-1.0\n",
      "-1.0\n",
      "-1.0\n",
      "1.0\n",
      "-1.0\n",
      "1.0\n",
      "-1.0\n",
      "-1.0\n",
      "1.0\n"
     ]
    }
   ],
   "source": [
    "predict_us = [[0,10],\n",
    "              [1,3],\n",
    "              [3,4],\n",
    "              [3,5],\n",
    "              [5,5],\n",
    "              [5,6],\n",
    "              [6,-5],\n",
    "              [5,8],\n",
    "              [2,5], \n",
    "              [8,-3]]\n",
    "\n",
    "for p in predict_us:\n",
    "    predict(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimized a step!\n",
      "Optimized a step!\n",
      "Optimized a step!\n",
      "[1 7] : 1.271999999999435\n",
      "[2 8] : 1.271999999999435\n",
      "[3 8] : 1.0399999999995864\n",
      "[5 1] : 1.0479999999990506\n",
      "[ 6 -1] : 1.7439999999985962\n",
      "[7 3] : 1.0479999999990506\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAD8CAYAAAB+UHOxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xl8W9Wd9/HPkS3bsR1ns7Lj7BDKDiFAKBDWJoEUQnxVlkCg7QQ60AJlWqB9hpR2WqAzDO3T8ExLKUtpWaRAFhIgCXtLgUIoDSSEgUAcnJBY2bwvWs7zh3SF7EiOZS1X0v29Xy9eieVr3SPA33PO7957jtJaI4QQwn4cVjdACCGENaQDEEIIm5IOQAghbEo6ACGEsCnpAIQQwqakAxBCCJuSDkAIIWxKOgAhhLAp6QCEEMKmiq1uQG+qq6v1+PHjrW6GEELkjfXr1+/WWrv6cmxOdwDjx4/nnXfesboZQgiRN5RSdX09VkpAQghhU9IBCCGETUkHIIQQNiUdgBBC2JR0AEIIYVPSAQghhE1JByCEEDYlHYAQQuSI1tZWvF4vd999d1bOJx2AEEJYyAx9wzBwuVy43W7uu+8+/H5/xs+d008CCyFEIWptbeXZZ5/F6/WyevVq2traGD58OFdddRWGYXD66adTVFSU8XZIByCEEFmQKPSvvPJK3G531kI/lnQAQgiRIW1tbTz77LN4PJ6cCf1Y0gEIIUQaxQt9l8vFlVdeGS3vFBfnRvTmRiuEECKPmaHv9XpZtWpVTod+rNxrkRBC5IFEoX/FFVdEyzu5GPqxcrt1QgiRQ9ra2njuuefweDwHhL5hGJxxxhk5H/qx+txSpdSDwAVAg9b6yMhr/wnMBbqALcDVWuv9cX52K9AMBIGA1npa6k0XQojMM0PfHOm3trbmdejHSqbVDwNLgD/GvLYOuE1rHVBK3Q3cBtyS4OfP1Frv7lcrhRAii+KFfnV1NQsWLMj70I/V50+gtX5NKTW+x2trY758E6hNT7OEECK7EoX+5ZdfjtvtLpjQj5XOT/NN4MkE39PAWqWUBn6ntb4/jecVQoh+aW9v71bTjw19wzCYOXNmwYV+rLR8MqXUj4EA8OcEh5yqtd6hlBoOrFNKbdZav5bgvRYBiwBqamrS0TwhhIgyQ9/r9fLMM8/YLvRjpfwplVILCV8cPltrreMdo7XeEfmzQSm1DJgOxO0AIrOD+wGmTZsW9/2EECIZ8UJ/2LBhtgz9WCl9YqXULMIXfc/QWrclOKYCcGitmyN/Pw/4aSrnFUKIg2lvb+f555+PlndaWloYNmwYl112GW6327ahHyuZ20AfB2YC1UqpemAx4bt+SgmXdQDe1Fpfq5QaDTygtZ4DjACWRb5fDDymtX4+rZ9CCCH4MvTNkb4Z+pdeeimGYXDmmWfaPvRjJXMX0KVxXv5DgmN3AHMif/8UOKZfrRNCiIM4WOjPnDkTp9NpdTNzknSFQoi8kyj0L7nkkmh5R0L/4KQDEELkhY6OjmhNX0I/PaQDEELkLDP0vV4vK1eu7Bb6Zk1fQr//pAMQQuSU2NB/5plnaG5uZujQoRL6GSAdgBDCch0dHaxZsyZa3jFD3+1243a7JfQzRDoAIYQlegt9wzA466yzJPQzTDoAIUTWmKFv1vQl9K0lHYAQIqPihf6QIUMk9HOAdABCiLTr6Ohg7dq1eDyebqFvGAZut1tCP0dIByCESAsz9L1eLytWrOgW+oZhcPbZZ0vo5xjpAIQQ/RYb+itXrqSpqUlCP49IByCESEpnZ2e3mr4Z+rW1tRL6eUY6ACHEQXV2dnar6ZuhP3/+/GhNv6SkxOpmiiRJB5AmwVCQIkeR1c0QIm3M0Ddr+rGhb470JfTzm3QAaVC3v45pv5/G+kXrqRkk21iK/BUv9AcPHiyhX6CkA0iDxa8sZm/7Xha/vJiHLnrI6uYIkZTOzk7WrVuHx+PpFvoXX3wxbrdbQr+ASQeQorr9dTy58UlCOsQTG5/gjjPvkFmAyHlm6Jsj/cbGRgl9G5IOIEWLX1lMMBQEwtcBZBYgclWi0J83bx6GYXDOOedI6NuMI5mDlVIPKqUalFIfxLw2VCm1Tin1ceTPIQl+dmHkmI+VUgtTbXguMEf//pAfAH/IzxMbn2Bb4zaLWyZEWGdnJ6tWrWLhwoWMGDGCuXPnsmLFCubNm8fq1avZtWsXDz30EHPmzJHwt6GkOgDgYWBWj9duBV7UWk8BXox83Y1SaijhTeRPAqYDixN1FPkkdvRvMmcBQlilq6uL1atXHxD6F110EatXr6ahoUFCXwBJloC01q8ppcb3ePlCYGbk748ArwC39Djma8A6rfVeAKXUOsIdyeNJtTaH9Bz9m8xZgFwLENnU1dUVLe8sX76cxsZGBg0axEUXXYRhGJx77rkS9uIA6bgGMEJr/QWA1voLpdTwOMeMAT6P+bo+8toBlFKLgEUANTW5G6C3v3z7AaN/UzAU5PaXb+fhix7ObqOErcSG/ooVK9i/f7+EvkhKti4Cqziv6XgHaq3vB+4HmDZtWtxjrFa3vw7PJs8Bo3+TP+TnyY1PcsfMOxg3eFyWWycKWVdXFy+88EL0ls2eoX/OOedQWlpqdTNFnkhHB7BLKTUqMvofBTTEOaaeL8tEAGMJl4ryUm+jf1MwFGTxK4tlFiBSlij0L7zwQtxut4S+6Ld0dAArgYXAXZE/V8Q5Zg3wi5gLv+cBt6Xh3Fl3sNG/SWYBIhVm6Js1/djQN8s7EvoiVUl1AEqpxwmP5KuVUvWE7+y5C/Aopb4FbAOMyLHTgGu11t/WWu9VSv0MeDvyVj81Lwjnm76M/k0yCxDJiBf6VVVV3Wr6EvoinZTWOVlmB8LXAN555x2rmxFVt7+OqfdNpSPQ0eefKSsuY/N1m2UWIOLq6urixRdfxOPxSOiLtFBKrddaT+vLsfIkcBKSGf2bZBYgejJD3+v1smzZsmjomzV9CX370lrT0vJPKiuPQal4986kl3QAfRTSIbybvACUFvX9lzOkQ3g2enjwwgdxqGSfuxOFIjb0ly9fzr59+6KhbxgG5513noS+zdXXL6G+/l46Oj7lhBPWM3Dg8Rk/p3QAfeRQDhp+0EBXsCvpny0pKpHwtyEJfZFIeKT/Lj7fU4wb9+8UFQ0gGGxhwIApjBv3YwYMmJSVdkgHkITKkkqrmyBynN/v71bTN0P/61//Om63W0LfxszQb2jw4vN56ej4FKWKGTp0NoMHn8a4cbcybtwBK+lklHQAQqTIDH2zpi+hL0xaa0KhNoqKKmhpeY/166ehVDGDB5/NuHE/prr6IpzOoZa1TzoAIfohNvSXL1/O3r17GThwYLfyTllZmdXNFBYIj/T/QUODB5/Py5AhZ3HYYb+nsvJYDj/8TwwdOgunc5jVzQSkAxCiz/x+Py+99FK0vCOhL3ratu0/2bHjt3R0fAoUMWTI2QwefDYASilGjLjc2gb2IB2AEL0wQ98s75ihH1vesSr0g6EgRY4iS84tzJH+e+zZs5px436EUg46O7czYMBkampuo7r6IkpKqq1uZq+kAxCih95C3zAMvva1r1k+0q/bX8e0309j/aL1sux4Fpmh7/N5aWjw0NGxBSjC5ZpHRcURTJ58b1bu308X6QCEID9CP9biVxazt32vbEGaBVprtO7C4Shl3751bNjwNcLlnbOoqbm120g/n8IfZCkI0U9b9m7hnjfu4U8b/kRLVwuVJZUsOHoBN59yM5OGZvYe5nSd2+/38/LLL+PxeKKhX1lZGa3p51rom2KXJCkrLuOj6z+SWUCaxY70fT4vw4dfwoQJPyMU6mTnzkdzuryTzFIQ0gGIpD338XPUemvxB/3dVkV1Opw4i5wsNZYye8rsnDy3Gfper5enn346GvpmTT9XQz/WVcuv4rH3H8Mf8uN0OLn8qMtlFpBGW7f+jF27/kh7+yeYI/3Ro6/B5ZpvddP6RDoAkTFb9m7h6N8eTZu/LeEx5c5yNly7Ie0zgf6eOzb0ly1bxp49e6Khb470BwwYkNa2Zkq8BQllFtB/5to7jY1/YezY7wKwceM3CAT24XIZVFfPy9mRfiKyGJzImHveuAd/8CB7IQT93PvmvSyZs8Syc//qvF91K+/kc+jHWvzK4gMWJAyGgnItIAlm6Jvlnfb2jwlfyDUoLR3JV77yOMomS7fIDEAkperOKpq7mg9+XGkVjbc2ZvfcQWArODc7qfq0Khr6c+fOjZZ38jH0Tb0tRy6zgN6FL+QGcTiK2bXrcT788DLC5Z0zcbnceTnST0RmACJjWrpa0npcyueOhD4bgQ+BdvCX+Dlv/nkFEfqxeluOPBgKcvvLt8uy4zG01rS2bog+kTt27A2MGXMdQ4eex6GH/i4S+i6rm2kp6QBEUipLKvs0A8jEwnnRc8eG/magDSgBDgWOgIFHDOSxf38s7ee30sG2IpUtSL+ktWbr1ttpaHgyWt4ZMuRMysrGA+B0DmP06EWWtjFXpFzoUkodppR6L+afJqXUjT2OmamUaow55vZUzyusseDoBTgdzl6PcTqcXHH0FWk9byAQYGZoJuoZBfcAjwLvAxOBbwA/AGrBeYSTK0+4Mq3nzgV92YzI3HzIbsya/s6djwDhe/H373+NsrJxHHro75gx4wuOOWYdw4adb3FLc09arwEopYqA7cBJWuu6mNdnAv+mtb4gmfeTawC5J5t3AQUCAV555ZXoLZu7d+/uNtJnMtCjL8rUHUhWSmYrUrtsQfpleceLz+ehvf1jHI4yTj11N0VFFYRCARwOexY4krkGkO5L3WcDW2LDXxSWSUMnsdRYSrmz/ICZgNPhpNxZzlJjab8DOBAI8MILL3DNNdcwatQozj33XP785z9zzjnn8NRTT7HsnWWUX1qO8whnt/BPx7lzVTJbkRbyLCB8ITcEwPbt9/HOO8eybdudlJbWcOihv+Xkk+soKqoAsG34JyvdM4AHgXe11kt6vD4TeAqoB3YQng1sTPAei4BFADU1NSfU1Ulfkou27N3CvW/ey6MbHo0+jXvF0Vdw08k3JR3A8Ub6FRUVzJ07F8MwmD17drcLuek8d65LZvRvKqRZQHik/35k7R0vEyf+HJdrPu3tn7Fv39rIhdzhVjczp1jyIJhSqoRwuB+htd7V43tVQEhr3aKUmgP8Wms95WDvKSWgxKxciiEdAoEAr776Kh6Pp0+hb1cLly3k8Q8eT3jxNx6nw8llR12W13cEhUKd1NX9Bw0NXtrbPwIcDB48k5qa2xg69Byrm5fTrOoALgSu01qf14djtwLTtNa7eztOOoD4rFyKIRVm6JsjfZ/PR0VFBRdccAFut5tZs2ZRXl5udTNzRkiHqPxFJYFQIKk9pUM6RLGjmJYfteTNXtThkf4HtLdvweW6CK01f//7VEpLx+JyGbhcF8tIv4+seg7gUuDxBA0aCezSWmul1HTC1x72pPHctrFl7xZqvbVxL8L6Q+EOodZbmzMXQnsLfXOkL6Efn0M5aPhBA13BrqR/tqSoJOfD3wx9n88THek7nS6qq+eiVBEnnrgBh0O20syktHQASqly4FzgmpjXrgXQWv8WqAW+o5QKAO3AJTqXH0HOYVYuxdBXgUCA1157LVre8fl8lJeXdyvvSOj3TSaep7CS+WuvlKKu7qds3foTwuWdMxg79kZcrnmEbyZEwj8LZCmIPGPlUgy9MUPf6/Xy1FNPSeiLqPBIfyM+X/iJ3MMOe4BBg06lufk9mpreiJR3RljdzIIhS0EUMCuXYugpUeibNX0JfXsLBJr4/PN78Pk8tLVtxhzpm4POgQOPZeDAY61tpM1JB5BnrFyKASAYDHar6Tc0NERD3zAM5syZI6FvU+ZI3+/fxZAhZ+NwlLF9+31UVh7NmDHfk5F+DpIOIM8sOHoBD7z7QK+3BaZ7KYZgMNitpi+hnxtyYVP4L8s73uhIf8CAwzjppM04HCWccsqXD2eJ3CMdQJ65+ZSbeeSfj/TeARQ5uenkm1I6jxn6ZnnHDP3zzz8/Wt6pqJBfbKvkyqbwn3xyI9u3/1/C5Z3ToyN9k4R/bpMOIM+YSzEc7DmA/twCGhv6Tz/9NLt27ZLQz1FWbArf2roxurTykUeupLx8MtXV8ygvP4zq6ospLR2ZlXaI9JG7gPJUupZDCAaD/OUvf4mWd2JD3yzvSOjnlmxuCu/376G+/jeR8s6HgGLQoNOZPPkeBg48ISPnFKmRPYFFr+KF/oABA7rV9CX0c1emN4Vvbd1IMNhCVdVJ+P17+dvfRlNVdTLDh7tlpJ8HpAMQBzBD36zpm6Fvlnck9PNDpjaFD5d3wnvktrVtYtCg0zjuuNcACAQaKS4elHLbRXbIcwAC6D30DcPg/PPPl9DPM5nYFP7DDxeya9cfCZd3TmPKlCVUV395IVfCv3BJB1BggsEgf/3rX/F4PBL6BaZufx1PbnzygDvA/CE/T2x8gjvOvOOgs4DW1k34fF52717OMce8iNM5lOrqixg48ERcrvmUlo7K5EcQOUY6gAJghr450t+5c6eEfgHq76bwnZ07+eKL+2lo8NDWthFzpN/VtQuncygu17zMNlzkLOkA8lSi0J8zZ060pl9ZWVgLidlZspvCt7Z+CISoqDiCYLCZrVt/wqBBpzF58m9kpC+ipAPII72FvjnSl9AvTH3ZFnJ0aYCn37iIU4f5aWvbiMtlcMQRHsrLpzBjxk5ZT18cQDqAHBcMBnn99dejNf2dO3dSVlbWrbxjdehbuSRBLiyHkGkHG/0D/McRcGp1gJB+j5CaHh3pmyT8RTzSAeQgM/S9Xi9Lly7NydA3WbkkQa4sh5BpPUf/NeUw0wXThsD3/wkBDa/vgXf2wRt7i5l12OE8fOL1FrZY5AvpAHJEbOg/9dRTfPHFF5SVlUVr+rkU+rGsWJIgF86dLebof1Cxn9kjw8E/sRJCGt5vhCEl4OuE53aaPxHodi1AiN7Ig2AWCoVC3co7saFvGAYXXHBBToa+KZtLEuTSubOltXUzP3zhR/x+wyoOq/Tz62PDof+qD17bDXsS7BRZCJvCi/6z5EGwyEbvzUAQCPRsgFJKAb8G5gBtwFVa63fTdf58YYa+Wd7Jt9CPFftQUqoPI+XTuTOptXVzdGnl1tYPKGktAhx80lrCgrdhb5cCvx9CIaIbJhY5oNgZfY+QDuHZ6OHBCx/M+X2BhbXSNgOIdADTtNa7E3x/DvBdwh3AScCvtdYn9faehTIDSBT6s2fPjpZ3Bg4caHUzk5KpJQly/dyZ9I9/zKSx8VUABg36Ki6XQfmgWVBc/eVBn38OJ50EnZ1fvlZaCn//O4wdG32ppKik4PYTFn2Tq0tBXAj8MbIZ/JtKqcFKqVFa6y+y2IasiQ39p556ih07duR96MfKxJIE+XDudGlr+4iGBi/NzX/nyCNXoJRi2LDzcbkujtynPyb+D/7i+9AagtgbggIh+MW98FB+fHbRO5/Px6ZNmzjjjDMyfq50zgA+A/YBGvid1vr+Ht9fBdyltf5r5OsXgVu01gmH+Pk2AwiFQvztb3+L1vRjQ98s7+Rz6JvijcBNmR6JW3nuVHV01LFz56OR8s77AFRVncpRR63E6Rx68Deoq4OpU6HjwM9OWRl89BHU5OZnF73z+Xw8/fTTeL1eXn75ZQYPHszOnTtxOp0H/+EerJoBnKq13qGUGg6sU0pt1lq/FtuuOD9zQO+jlFoELAKoyYP/mc3QN8s7O3bsoLS0tFtNvxBCP1Z/lyTI93P3R1vb/1JcPIiSkhE0Nb3N1q3/TlXVqUye/Cuqq+dTVjb24G9iuv12CCZ4GCwYDH//4YfT0m6ReT6fj2XLluHxeHjllVcIBoMceuih3HbbbRiGQXFx5gs0GbkLSCn1E6BFa/1fMa/9DnhFa/145OuPgJm9lYBydQaQKPTN8k4hhr6ptxG4qay4jM3XbU77bYhWnjsZbW3/i8/npaHBQ2vrBiZM+Dnjxv2IYLAdv39PcqFv6m30byorg82bYZzc/pmr4oX+lClTcLvdGIbB0UcfTfh+mf7L+gxAKVUBOLTWzZG/nwf8tMdhK4HrlVJPEL4I3JhP9f9QKMQbb7wRLe9s3749GvqGYTB37tyCDf1YfVmSIBgKsviVxWkfiVt57r7QOsi7755Cc/PbANGRvstVC0BR0QCKivoR/tD76N8UDMLixTILyDFm6JvlHTP0b7311rSFfn+lZQaglJoILIt8WQw8prX+uVLqWgCt9W8jt4EuAWYRvg306t7q/2D9DEBCv7u+jMBN6R6JW3nuRMyRfnv7Z0yd+gAAW7bcQmnp6OTLO73py+jfJLOAnJAo9A3DwO12ZzT0sz4D0Fp/ChwT5/XfxvxdA9el43yZZIa+Wd6JDf1f/vKXXHDBBVRVVVndTEv0ZQRuSvdI3Mpzx2pv/4yGhsdoaPDS2vpPIHzLZijUicNRyqRJd6f9nH0a/ZtkFmCZ3bt3R8s7ZuhPnjyZW265BcMwOOaYYywb6SciTwKTOPRnzZoVrenbNfRNyYzATekaiVt5boC2to8pKRlBcXEV9fVL+OST71JVNQOXy8Dlqk3fSD+eZEb/JpkFZI0Z+l6vl5deeika+mZN34rQz9XnAHJKKBTizTffxOPxHBD6d999N3PnzrV96MdKZgRuStdI3Ipzt7V9HHMh958cdtgDjBr1LUaMWEB19YWUlR3Sr/dNWjKjf5PMAjIqUejn8kg/EVvNAMzQ93q9eL3ebqFv1vQl9A8U0iEqf1FJIBRIammBkA5R7Cim5Uct/V6SIN65NZqu4IEL4ZQUlaAidxv399yBQAvvvXcaLS3vAURH+sOHuyktHd2vz9BvoRBUVkIgAI4k/v2FQlBcDC0tyf2cSChR6Js1/VwKfZkBxIgN/aVLl1JfX09JSQmzZ8+WkX4fOZSDhh80xA3dgykpKklpPZp4575u9XUs3bSUgA5EXytWxcyfOp8l5y9J6tzmSD8YbGbixDspLq6ksvJ4RoxYiMs1P3sj/XgcDmhogK7k/71TUiLhn6I9e/ZEa/qxof/DH/4QwzA49thjcyb0+6sgZwCJQt+s6Uvo5690PAnc3v4pDQ1P4PN5oyP9wYPP4phjXsj7X2iRGjP0vV4vL774IsFgkEmTJkVr+vkQ+raeAbS2tvKVr3yFbdu2RUP/zjvvZO7cuQwaNMjq5okU9fdJ4La2Tygrq8HhKOGLLx5k27afU1V1MpMm/XfkQq6FI31hqUSh/4Mf/AC3250Xod9fBTkDuPXWWznyyCMl9AtMsk8Ct7V9Ella2UtLyz846qjVDBs2h87OnWjtl9C3sUShb9b08zn0bT0DALjrrrusboLIgL4+CXzXqz/kW2M+pqXlHwCRkf49VFYeB0Bp6ciMt1Xknj179rB8+XI8Hs8BI33DMDjuuOPyNvT7qyA7ALux+8boo8vgDFd4b1xvvZ9HPljB1YecxqRJ90TKO7m/qKDIDDP0zZF+IBBg4sSJtg79WNIB5Dm7bow+qiy8P+5MFxwaWY3jr7vBWw+BUIj/t20MDx//fYtaK6yUKPRvvvlm3G637UM/VkFeA7CTq5ZfxaMbHuXKo6/Mm81QkmXW/gcXd7AzUv7/t0Ph/FGwqQle8YX3yW2I2SQrF1YFFdmzd+/ebuUdM/QNw8AwDI4//njbhH4y1wCkA8hjdtgYvb39U+572WBQ8F2mDIRF6+HjFhhZBlrDrs74PycboxegLVvgnnvgT3+Clhb2VlSwfNo0vKEQL/ztb7YO/VjSAdjEVcuv4rH3H8Mf8uN0OLn8qMsLZhbQ1vYxmzZdSkvLegA+bFL8ZY+DFxuKaPQf/Jc6HU8hixzy3HNQW8veri6WBwJ4gReAADBBKdy1tRi33GLb0I8lHYANFNrG6O3tn+LzeXE6RzBq1FUEg+1s2DCb6uq5lA+ajXImf+eObIxeGPauX8/yGTPwdnV9GfqAAbiB4wFVXg4bNsCkSVY2NSfY/jZQOyiEjdHN0G9o8EZH+iNGXMmoUVdRVDSA4457xdoGCsvs27cvWtN/Ye1aAqEQE4DvEw7+E+ixx6zfD/feC0uWxHs7kYDMAPJQPm+M3tm5I7qo2vvvz2XPnlUMHDid4cPdkVs25aKtXZmh7/V6WbduHYFAgPHjx+PesQOjq+vA0O+pqgoaG7PU2twlM4ACl28bo3cf6b/LySfXUVZ2CBMn3sXkyb9hwIDxVjdRWCQ29F944QX8fj/jx4/n+9//PoZhcMIJJ6CK+viMS0tLZhtbgFLuAJRShwB/BEYCIeB+rfWvexwzE1gBfBZ56Wmtdc89g0Uf9PZAFIA/5OfJjU9yx8w7LL8Fsrn5H3z00b9EyzsDB57IxIl3U1RUDkBFxRFWNk9YJFHo33jjjbjd7nDox17IrayE5uaDv3GlXO9JVjpmAAHgZq31u0qpgcB6pdQ6rfWmHsf9RWt9QRrOZ2u5vDF6e/tn+HxLKS+fSnX1XEpKRqFUMRMn/hKXq5YBAyZktT0id+zbt48VK1aEa/o9Qt8wDKZNm5b47p0FC+CBB8J1/kScTrjiisw0voCl/RqAUmoFsERrvS7mtZnAvyXbAcg1gO5ycWN0M/R9Pg/NzeH/VmPGXM+UKb/J6HlF7jND36zp+/1+xo0bF11audfQj7VlCxx9NLS1JT5G7gKKsuwagFJqPHAc8Facb5+ilPonsINwZ7Axnee2g1zZGN3v34PTOQyATZvcNDe/w8CB02SkLxKG/g033IDb7e576MeaNAmWLoXa2vAsIHYm4HSG/1m6VMK/H9I2A1BKVQKvAj/XWj/d43tVQEhr3aKUmgP8Wms9JcH7LAIWAdTU1JxQV1eXlvblO6s3Rm9v3xpdWrm19QNmzGiguLiSpqa3cDqHS+jb2P79+6PlndjQN5dW7lfox7NlS/hWz0cfDV/wrawMl31uuknCP0bWHwRTSjmBVcAarfV/9+H4rcA0rfXu3o6TEtCXFi5byOMfPJ7w4m886VgOYf/+v7Jly/dpbn4bgIEDp+FyGYwefQ3FxbLXgl31FvqGYXDiiSfa/olcq2S1BKTC/5X/AHyYKPyVUiOBXVprrZSaDjiAPame2y5COoR3kxeA0qLmQAUjAAARw0lEQVTSpH7Os9HDgxc+2OflEMIj/aVUVZ3M4MFfpbh4EFqHmDjx7kh5Z2K/PoPIf2boe71e1q5di9/vp6amhhtuuEFCP0+l4xrAqcAVwPtKqfcir/0IqAHQWv8WqAW+o5QKAO3AJTqXn0DLMZnelL2jo46GhnB5p7n57wCMG/d/GDz4q1RWHsW0aTILs6tEof+9730Pt9stoZ/n5ElgmwoEmigurkJrzZtvjqOz83MqK0+IPpErI3372r9/PytXrsTj8XQLfbO8M336dAn9HCZPAou4Ykf6HR11zJixHaWKmDr1IcrKJkjo25gZ+l6vlzVr1nQb6UvoFy7pAGxg7951fPbZ/4mWdyorj2fs2BsJhTopKipnyJCzLW6hsIKEvpAOoAB1dNTh8y1l6NBZkeUWFFoHmDDhToYPNxgwQG6Zs6vGxsZuNf2uri4OOeQQvvvd7+J2uyX0bUY6gAJhhn5Dg5fmZvM5PEVFxREMHXoOQ4eut7R9wjqNjY3davpm6F9//fUYhsFJJ50koW9T0gHksWCwnaKiAYRCXbz99lEEg81UVh4vI30RDX2zvNMz9KdPn47DITul2Z10AHmmo2NbZO0dL8FgKyeeuAGHo4TDD3+UioojJfQLXY99camsDC+WdvPNNFZXS+iLpMhtoHli9+6VbNt2J01NbwJQWXkcLpdBTc0PUaqP66WL/BbZFzd2PZxGYGVREV5gjVJ0BQIccsgh1NbWRmv6Evr2IreBFoCOjs/x+ZbichmUlY0lEGgkFOpkwoRf4HIZlJdPtrqJIpu2bAmHf1sbTcBKwAOsAbqCQcYC1xUXY3g8nDR/voS+6BPpAHKIGfo+n5empjcAKC4ewqhRVzFixAJGjpT1zu2q6c47WdnZiRd4HuiCcOgT3iP3JMChFLz6KhiGhS0V+URKQBYLhbpwOErw+/fx+usuIEhl5bG4XG4Z6dtcU1PTlzX9lSvpJBz6tYCbSOj3/CHZF9f2pASU42JH+kVFAznmmDU4nUOYOvUhqqpOprw87krZwgaampp45pln8Hg8rFmzhs7OTsaOHct36CX0Y8m+uCIJ0gFkUUODh/r6X0XLO5WVx1JdfVH0+1LisaeEof+d72AYBieffDKOwYNlX1yRdtIBZFBHRz0+31JGjfoWxcUD6ejYRijUzoQJP4+Ud2Skb1dm6Hu9Xp5//nk6OzsZM2ZM99CPvZAr++KKDJBrAGlmhr7P54mO9I88cgXV1V9H6xCqj+vyi8KTKPTNWzYPCP1Ysi+u6CO5BpBlWgdRqoj29k95663wL19FxTFMmPAfkZH+oQAS/jbU3NwcLe/Ehv61116LYRiccsopfbtlU/bFFRkgHUA/fTnS9zJgwGQOP/wRBgyYyJQpSxgy5Nxo6Av7MUPf6/Xy3HPP9T/0e5o9OzzCl31xRZpICShJO3c+yo4dv6Wp6W8AVFQczciRV3PIITda3DJhpXihP3r06OgmKv0OfSGSlPUSkFJqFvBroAh4QGt9V4/vlwJ/BE4gvBfwN7TWW9Nx7kzr7NzO7t3LGTXqGhyOYlpa3iMYbDmgvCPsJ1HoX3PNNbjdbgl9kfPSsSl8EXAfcC5QD7ytlFqptd4Uc9i3gH1a68lKqUuAu4FvpHruTOns3B5dWrmp6XUgvPbOoEEzmDjxLhwOp8UtFFZpbm5m1apVeDyeA0LfMAxmzJghoS/yRjpmANOBT7TWnwIopZ4ALgRiO4ALgZ9E/r4UWKKUUrm0MbzWGqUUTU1v8+670wGoqDiK8eN/xvDhBuXlhwFI+NuQGfrmSL+jo4NRo0ZJ6Iu8l44OYAzweczX9YQfWIx7jNY6oJRqBIYBu9Nw/n7r7NwRvZBbVTWDSZPuprLyOCZMuJPq6ouoqJhqZfOEhRKF/r/8y7/gdrsl9EVBSEcHEG8roZ4j+74cEz5QqUXAIoCamprUWpbAF1/8gZ07H6ax8XVAU1FxFGVlEwBwOIoZN+7WjJxX5DYJfWE36egA6oFDYr4eC+xIcEy9UqoYGATsjfdmWuv7gfshfBdQGtpHZ+cO9u1bx8iRCwHYt+8lAoFGxo+/A5fLkJG+jbW0tHSr6ceGvmEYnHrqqRL6omClowN4G5iilJoAbAcuAS7rccxKYCHwBuHFDF/KdP0/XN55Cp/PEx3pV1WdQnn5oRx22B8oKirL5OlFDjND3+v18uyzz0roC9tKuQOI1PSvJ7w3RRHwoNZ6o1Lqp8A7WuuVwB+AR5VSnxAe+V+S6nl7s2fP87z//hzC5Z0joyN985ZNCX/7SRT63/72t3G73RL6wpYK8kGwQKCJ+vpfRco7h2egZSIftLS0sHr1ajweT7fQnz9/fnSkX1Qk22mKwmL7tYCKi6sYP/52q5shLBAv9EeOHMm3v/1tCf1U9bIhvSxDkZ8KcgYg7MUMfbO8097ezsiRI6mtrZXQT5c4G9ID3Reimz3buvaJKNvPAEThSxT63/zmN6M1fQn9NInZkP4AZodQWytLUech6QBE3mhtbe1W3okNfcMw+OpXvyqhnwn33NP7RjQQ/v6998KSJdlpk0gLKQGJnGaGvtfrZfXq1bS3tzNixIhoeUdCPwuqqvq2HaVsSJ8TpAQk8lqi0JeRvkX6utG8bEifd6QDEDkhUehfffXVuN1uCX0rVVbKhvQFSjoAYZnW1laeffZZPB7PAaFvGAannXaahH4ukA3pC5Z0ACKrzNA3R/ptbW0MHz5cQj+X3XwzPPLIwTuAm27KXptEWkgHIDIuUegvXLgQt9stoZ/rZEP6giUdgMiItra2buUdCf08JxvSFyS5DVSkTaLQN9feOf300yX0hcgwuQ1UZI0Z+l6vl1WrVnUb6UvoC5HbpAMQSUsU+ldeeSVut1tCX4g8IR2A6JO2tjaee+45PB7PAaFvjvSLi+V/JyHyifzGioTM0DdH+q2trbhcLgl9IQqE/PaKbhKF/hVXXCGhL0SBSek3WSn1n8BcoAvYAlyttd4f57itQDMQBAJ9vUItsiNR6C9YsCBa05fQF6LwpPpbvQ64LbIv8N3AbcAtCY49U2u9O8XziTRpb2/vVtOPDX3DMDjjjDMk9IWIJxiEArnJIaXfcK312pgv3wRqU2uOyCQz9L1eL8888wytra1UV1dL6AvRV3V1MG0arF8PNTVWtyZl6fxt/ybwZILvaWCtUkoDv9Na35/G84peSOgLkUaLF8PeveE/H3rI6tak7KBPAiulXgBGxvnWj7XWKyLH/BiYBlys47yhUmq01nqHUmo44bLRd7XWryU43yJgEUBNTc0JdXV1yXweQeLQv/jii3G73RL6QvRHXR1MnQodHVBWBh99lJOzgLQ+Cay1PucgJ1sIXACcHS/8I++xI/Jng1JqGTAdiNsBRGYH90N4KYiDtU+Etbe38/zzz0dr+i0tLVRXV3P55ZdjGAYzZ86U0BciFYsXh+v/EP6zAGYBqd4FNIvwRd8ztNZxdowGpVQF4NBaN0f+fh7w01TOK8LM0DdH+i0tLQwbNozLLrtMQl+IdKqrgyef/HIlVL8fnngC7rgjJ2cBfZVqOiwBSoF1SimAN7XW1yqlRgMPaK3nACOAZZHvFwOPaa2fT/G8tpUo9C+99FLcbreEvhCZEDv6NxXALEBWA80D7e3trFmzBo/H0y30zZq+hL4QGRRb++8pB68FyGqgBaCjoyNa0+850jcMgzPPPFNCX4hsuP32A0f/pmAw/P2HH85qk9JFZgA5xAx9r9fLypUru430zZq+0+m0uplC2Edvo39TWRls3gzjxmWvXb2QGUAeiQ39Z555hubmZoYNG8Yll1wSLe9I6Athkd5G/ybzWkAezgJkBmCBjo6ObjV9M/TnzZsXLe9I6Athsb6M/k05NAuQGUAOMkPfLO+Yof+Nb3xDQl+IXNSX0b8pT2cBMgPIoHihP3To0GhNX0JfiByVzOjflCOzAJkBWChR6Lvdbtxut4S+EPkgmdG/KQ9nATIDSIOOjg7Wrl2Lx+PpFvpmTf+ss86S0BciX4RCUFkJgQA4HMn9XHExtLQk93NpJjOALDBD3+v1smLFim4jfQl9IfKYwwENDdDVlfzPlpRYGv7Jkg4gCbGhv3LlSpqamhgyZIiEvhCFprLS6hZkhXQAB9HZ2dmtpm+Gfm1tLW63W0JfCJG3pAOIo7Ozs1tNPzb0DcPg7LPPltAXQuQ96QAizNA3a/oS+kKIQmfrDiBR6M+fPz9a3ikpKbG6mULkngLaGN3ObNcBdHZ2sm7dOjwej4S+EP1RYBuj25ktOoDeQt8s70joC9FHBbYxup0VbAdghr5Z3mlsbGTw4MES+kKkwtwaMRQqiC0R7a7gOoDW1lb+9V//tVvoz5s3D7fbLaEvRKoKcGN0O0vpkTWl1E+UUtuVUu9F/pmT4LhZSqmPlFKfKKVuTeWcB1NeXs6HH37IvHnzWL16Nbt27eKhhx5i9uzZEv5CpCLRxujbtlnbLtFv6ZgB3Ku1/q9E31RKFQH3AecC9cDbSqmVWutNaTh3vPPx1ltvEdmEXgiRLgW6MbqdZWPRiunAJ1rrT7XWXcATwIWZPKGEvxBp1nP0b5JZQF5LRwdwvVJqg1LqQaXUkDjfHwN8HvN1feS1uJRSi5RS7yil3vH5fGlonhAiZX3ZGF3knYN2AEqpF5RSH8T550Lgf4BJwLHAF8A98d4izmsJ16DWWt+vtZ6mtZ7mcrn6+DGEEBlTVwcez4Gjf5PfH54d1NVlt10iZQe9BqC1Pqcvb6SU+j2wKs636oFDYr4eC+zoU+uEENYr8I3R7SzVu4BGxXw5D/ggzmFvA1OUUhOUUiXAJcDKVM4rhMiSg43+TTILyEupXgP4pVLqfaXUBuBM4CYApdRopdSzAFrrAHA9sAb4EPBorTemeF4hRDb0Z2N0kTdkS0ghRHx5vDG6nSWzJWT+7F0mhMiuVDZGF3lBOgAhxIFCIfB6w38vLe37PxC+ZhAKWdd20WcFtxaQECINbLQxup1JByCEiM8mG6PbmXTTQghhU9IBCCGETUkHIIQQNpXTzwEopXxAvjxaWA3stroRFpHPbj92/dyQ+599nNa6Twup5XQHkE+UUu/09eGLQiOf3X6f3a6fGwrrs0sJSAghbEo6ACGEsCnpANLnfqsbYCH57PZj188NBfTZ5RqAEELYlMwAhBDCpqQDSAOl1Cyl1EdKqU+UUrda3Z5sUEodopR6WSn1oVJqo1LqBqvblG1KqSKl1D+UUvF2witYSqnBSqmlSqnNkf/+p1jdpmxRSt0U+f/9A6XU40qpMqvblArpAFKklCoC7gNmA18BLlVKfcXaVmVFALhZa304cDJwnU0+d6wbCG9yZDe/Bp7XWk8FjsEm/w6UUmOA7wHTtNZHAkWEdzjMW9IBpG468InW+lOtdRfwBHChxW3KOK31F1rrdyN/byYcAmOsbVX2KKXGAucDD1jdlmxSSlUBpwN/ANBad2mt91vbqqwqBgYopYqBcvJ8f3PpAFI3Bvg85ut6bBSEAEqp8cBxwFvWtiSrfgX8ELDbwvcTAR/wUKT89YBSqsLqRmWD1no78F/ANuALoFFrvdbaVqVGOoDUqTiv2ebWKqVUJfAUcKPWusnq9mSDUuoCoEFrvd7qtligGDge+B+t9XFAK2CX615DCM/uJwCjgQql1AJrW5Ua6QBSVw8cEvP1WPJ8WthXSikn4fD/s9b6aavbk0WnAl9XSm0lXPI7Syn1J2ublDX1QL3W2pztLSXcIdjBOcBnWmuf1toPPA3MsLhNKZEOIHVvA1OUUhOUUiWELwqttLhNGaeUUoTrwB9qrf/b6vZkk9b6Nq31WK31eML/vV/SWuf1SLCvtNY7gc+VUodFXjob2GRhk7JpG3CyUqo88v//2eT5BXDZESxFWuuAUup6YA3huwIe1FpvtLhZ2XAqcAXwvlLqvchrP9JaP2thm0R2fBf4c2TA8ylwtcXtyQqt9VtKqaXAu4TvgvsHef5UsDwJLIQQNiUlICGEsCnpAIQQwqakAxBCCJuSDkAIIWxKOgAhhLAp6QCEEMKmpAMQQgibkg5ACCFs6v8DnPlPPaEGVwUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "class Hard_Margin_SVM:\n",
    "    def __init__(self, visualization=True):\n",
    "        self.visualization = visualization\n",
    "        self.colors = {1:'r',-1:'g'}\n",
    "        if self.visualization:\n",
    "            self.fig = plt.figure()\n",
    "            self.ax = self.fig.add_subplot(1,1,1)\n",
    "            \n",
    "    # 定义训练函数\n",
    "    def train(self, data):\n",
    "        self.data = data\n",
    "        # 参数字典 { ||w||: [w,b] }\n",
    "        opt_dict = {}\n",
    "        \n",
    "        # 数据转换列表\n",
    "        transforms = [[1,1],\n",
    "                      [-1,1],\n",
    "                      [-1,-1],\n",
    "                      [1,-1]]\n",
    "        \n",
    "        # 从字典中获取所有数据\n",
    "        all_data = []\n",
    "        for yi in self.data:\n",
    "            for featureset in self.data[yi]:\n",
    "                for feature in featureset:\n",
    "                    all_data.append(feature)\n",
    "                    \n",
    "        # 获取数据最大最小值\n",
    "        self.max_feature_value = max(all_data)\n",
    "        self.min_feature_value = min(all_data)\n",
    "        all_data = None\n",
    "\n",
    "        # 定义一个学习率(步长)列表\n",
    "        step_sizes = [self.max_feature_value * 0.1,\n",
    "                      self.max_feature_value * 0.01,\n",
    "                      self.max_feature_value * 0.001\n",
    "                      ]\n",
    "\n",
    "        \n",
    "        # 参数b的范围设置\n",
    "        b_range_multiple = 2\n",
    "        b_multiple = 5\n",
    "        latest_optimum = self.max_feature_value*10\n",
    "        \n",
    "        # 基于不同步长训练优化\n",
    "        for step in step_sizes:\n",
    "            w = np.array([latest_optimum,latest_optimum])\n",
    "            # 凸优化\n",
    "            optimized = False\n",
    "            while not optimized:\n",
    "                for b in np.arange(-1*(self.max_feature_value*b_range_multiple),\n",
    "                                   self.max_feature_value*b_range_multiple,\n",
    "                                   step*b_multiple):\n",
    "                    for transformation in transforms:\n",
    "                        w_t = w*transformation\n",
    "                        found_option = True\n",
    "                        \n",
    "                        for i in self.data:\n",
    "                            for xi in self.data[i]:\n",
    "                                yi=i\n",
    "                                if not yi*(np.dot(w_t,xi)+b) >= 1:\n",
    "                                    found_option = False\n",
    "                                    # print(xi,':',yi*(np.dot(w_t,xi)+b))\n",
    "                                    \n",
    "                        if found_option:\n",
    "                            opt_dict[np.linalg.norm(w_t)] = [w_t,b]\n",
    "\n",
    "                if w[0] < 0:\n",
    "                    optimized = True\n",
    "                    print('Optimized a step!')\n",
    "                else:\n",
    "                    w = w - step\n",
    "\n",
    "            norms = sorted([n for n in opt_dict])\n",
    "            #||w|| : [w,b]\n",
    "            opt_choice = opt_dict[norms[0]]\n",
    "            self.w = opt_choice[0]\n",
    "            self.b = opt_choice[1]\n",
    "            latest_optimum = opt_choice[0][0]+step*2\n",
    "            \n",
    "        for i in self.data:\n",
    "            for xi in self.data[i]:\n",
    "                yi=i\n",
    "                print(xi,':',yi*(np.dot(self.w,xi)+self.b))            \n",
    "    \n",
    "    # 定义预测函数\n",
    "    def predict(self,features):\n",
    "        # sign( x.w+b )\n",
    "        classification = np.sign(np.dot(np.array(features),self.w)+self.b)\n",
    "        if classification !=0 and self.visualization:\n",
    "            self.ax.scatter(features[0], features[1], s=200, marker='^', c=self.colors[classification])\n",
    "        return classification\n",
    "\n",
    "    # 定义结果绘图函数\n",
    "    def visualize(self):\n",
    "        [[self.ax.scatter(x[0],x[1],s=100,color=self.colors[i]) for x in data_dict[i]] for i in data_dict]\n",
    "\n",
    "        # hyperplane = x.w+b\n",
    "        # v = x.w+b\n",
    "        # psv = 1\n",
    "        # nsv = -1\n",
    "        # dec = 0\n",
    "        # 定义线性超平面\n",
    "        def hyperplane(x,w,b,v):\n",
    "            return (-w[0]*x-b+v) / w[1]\n",
    "\n",
    "        datarange = (self.min_feature_value*0.9,self.max_feature_value*1.1)\n",
    "        hyp_x_min = datarange[0]\n",
    "        hyp_x_max = datarange[1]\n",
    "\n",
    "        # (w.x+b) = 1\n",
    "        # 正支持向量\n",
    "        psv1 = hyperplane(hyp_x_min, self.w, self.b, 1)\n",
    "        psv2 = hyperplane(hyp_x_max, self.w, self.b, 1)\n",
    "        self.ax.plot([hyp_x_min,hyp_x_max],[psv1,psv2], 'k')\n",
    "\n",
    "        # (w.x+b) = -1\n",
    "        # 负支持向量\n",
    "        nsv1 = hyperplane(hyp_x_min, self.w, self.b, -1)\n",
    "        nsv2 = hyperplane(hyp_x_max, self.w, self.b, -1)\n",
    "        self.ax.plot([hyp_x_min,hyp_x_max],[nsv1,nsv2], 'k')\n",
    "\n",
    "        # (w.x+b) = 0\n",
    "        # 线性分隔超平面\n",
    "        db1 = hyperplane(hyp_x_min, self.w, self.b, 0)\n",
    "        db2 = hyperplane(hyp_x_max, self.w, self.b, 0)\n",
    "        self.ax.plot([hyp_x_min,hyp_x_max],[db1,db2], 'y--')\n",
    "\n",
    "        plt.show()\n",
    "\n",
    "\n",
    "data_dict = {-1:np.array([[1,7],\n",
    "                          [2,8],\n",
    "                          [3,8],]),\n",
    "             \n",
    "             1:np.array([[5,1],\n",
    "                         [6,-1],\n",
    "                         [7,3],])}\n",
    "\n",
    "svm = Hard_Margin_SVM()\n",
    "svm.train(data=data_dict)\n",
    "\n",
    "predict_us = [[0,10],\n",
    "              [1,3],\n",
    "              [3,4],\n",
    "              [3,5],\n",
    "              [5,5],\n",
    "              [5,6],\n",
    "              [6,-5],\n",
    "              [5,8],\n",
    "              [2,5], \n",
    "              [8,-3]]\n",
    "\n",
    "for p in predict_us:\n",
    "    svm.predict(p)\n",
    "\n",
    "svm.visualize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
